'''
Created on 30/09/2013

@author: daniel
'''
import unittest
import colecciones.cola

class MaxHeap(colecciones.cola.Cola):
    '''
    clase concreta que se asocia a la clase Heap para lograr una estructura de
    ordenamiento maxheap
    '''
    def agregar(self,elem):
        self.poner(elem)
        iHijo=self.getTamanio()
        while(self.__esMaxHeap__()==False):
            iPadre=(iHijo//2)
#             print "iHijo"
#             print iHijo
#             print "iPadre"
#             print iPadre
            if(elem.__cmp__(self.__datos__.elemento(iPadre-1))>0):
                aux=self.__datos__.elemento(iPadre-1)
#                 print "se reemplaza:"
#                 print aux
#                 print "por:"
#                 print self.__datos__.elemento(iHijo-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijo-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijo-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijo)
            iHijo=iPadre
           
    def eliminar(self):
        elem=self.sacar()
#         print self.__datos__.elemento(self.getTamanio()-1)
        self.__datos__.agregar(self.__datos__.eliminar(self.getTamanio()-1), 0)
        iPadre=1
        while(self.__esMaxHeap__()==False):
            iHijoR=(iPadre*2)+1
            iHijoL=iPadre*2
#             print self.__datos__
            if self.getTamanio()==2:
                aux=self.__datos__.elemento(0)
                self.__datos__.agregar(self.__datos__.elemento(1),0)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(0)
                self.__datos__.agregar(aux,1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(2)
            elif(self.__datos__.elemento(iHijoL-1).__cmp__(self.__datos__.elemento(iHijoR-1))>0):
                aux=self.__datos__.elemento(iPadre-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijoL-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijoL-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijoL)
                iPadre=iHijoL
            else:
                aux=self.__datos__.elemento(iPadre-1)
                self.__datos__.agregar(self.__datos__.elemento(iHijoR-1),iPadre-1)#guardo hijo en el lugar del padre
                self.__datos__.eliminar(iPadre)
                self.__datos__.agregar(aux,iHijoR-1)#guardo padre en el lugar del hijo
                self.__datos__.eliminar(iHijoR)
                iPadre=iHijoR
        return elem
    
    def __esMaxHeap__(self):
        if(self.getTamanio()<=1):return True
        if(self.getTamanio()==2):
            if(self.__datos__.elemento(1).__cmp__(self.__datos__.elemento(0))>0):
                return False
            else: return True
        i=2
        while(i-1<self.getTamanio()):
#             print "indice i"
#             print i
#             print "indice i/2"
#             print i//2
            if(self.__datos__.elemento(i-1).__cmp__(self.__datos__.elemento((i//2)-1))>0):
#                 print " no es max"
                return False
            i+=1
#         print "es max"
        return True

    def __str__(self):
        return self.__datos__.__str__()
    
    

class Test(unittest.TestCase):
 
    def testInit(self):
        self.assertIsInstance(MaxHeap(), MaxHeap,"Verifica la creacion de maxheap")

    def testPoner(self):
        obj=MaxHeap()
        obj.poner(23)
        self.assertFalse(obj.esVacia(), "verifica existencia de elemento")
    
    def testTope(self):
        obj=MaxHeap()
        obj.poner(4)
        obj.poner(3)
        obj.poner(2)
        obj.poner(5)
        self.assertEquals(obj.tope(),4, "verifica existencia del dato")
    
    def testSacar(self):
        obj=MaxHeap()
        obj.poner(5)
        obj.poner(10)
        self.assertFalse(obj.esVacia(), "verifica existencia de elemento")
        elim=obj.sacar()
        self.assertFalse(obj.esVacia(), "verifica la no existencia de elemento")
        self.assertEquals(elim, 5,"elemento eliminado")
    
    def testEsVacia(self):
        obj=MaxHeap()
        self.assertTrue(obj.esVacia(), "Verifica devolucion correcta")
        obj.poner(1)
        self.assertFalse(obj.esVacia(), "Verifica devolucion correcta")
    
        
    def testEsMaxHeap(self):
        obj1=MaxHeap()
        obj1.poner(41)
        obj1.poner(52)
        self.assertFalse(obj1.__esMaxHeap__(), "Verifica correcto no maxheap")
        
        obj=MaxHeap()
        obj.poner(54)
        obj.poner(52)
        obj.poner(41)
        obj.poner(50)
        obj.poner(52)
        self.assertTrue(obj.__esMaxHeap__(),"Verifica correcta devolucion de la funcion")

        obj2=MaxHeap()
        obj2.poner(54)
        obj2.poner(52)
        obj2.poner(50)
        obj2.poner(46)
        obj2.poner(41)
        self.assertTrue(obj2.__esMaxHeap__(),"Verifica correcta devolucion de la funcion")

        obj3=MaxHeap()
        obj3.poner(54)
        obj3.poner(52)
        obj3.poner(41)
        obj3.poner(50)
        self.assertTrue(obj3.__esMaxHeap__(),"Verifica correcta devolucion de la funcion")

        obj4=MaxHeap()
        obj4.poner(4)
        obj4.poner(3)
        obj4.poner(2)
        obj4.poner(5)
        self.assertFalse(obj4.__esMaxHeap__(), "Verifica correcta devolucion de la funcion")

        obj5=MaxHeap()
        obj5.poner(54)
        obj5.poner(50)
        obj5.poner(52)
        obj5.poner(41)
        obj5.poner(46)
        self.assertTrue(obj5.__esMaxHeap__(),"Verifica correcta devolucion de la funcion")

        obj6=MaxHeap()
        obj6.poner(5)
        obj6.poner(5)
        obj6.poner(5)
        obj6.poner(5)
        obj6.poner(5)
        self.assertTrue(obj6.__esMaxHeap__(),"Verifica correcta devolucion de la funcion")


if __name__ == "__main__":
    #import sys;sys.argv = ['', 'Test.testName']
    unittest.main()